Assignment 2: Implement program to find minimum and maximum element from given list using Divide and Conquer

on

 Problem Statement 

Implement program to find minimum and maximum element from given list using Divide and Conquer

Theory

METHOD 1 (Simple Linear Search) 

Initialize values of min and max as minimum and maximum of the first two elements respectively. Starting from 3rd, compare each element with max and min, and change max and min accordingly (i.e., if the element is smaller than min then change min, else if the element is greater than max then change max, else ignore the element) 

Time Complexity: O(n)
In this method, the total number of comparisons is 1 + 2(n-2) in the worst case and 1 + n – 2 in the best case. In the above implementation, the worst case occurs when elements are sorted in descending order and the best case occurs when elements are sorted in ascending order.

METHOD 2

Divide and Conquer Approach

In this approach, the array is divided into two halves. Then using recursive approach maximum and minimum numbers in each halves are found. Later, return the maximum of two maxima of each half and the minimum of two minima of each half.

In this given problem, the number of elements in an array is y−x+1, where y is greater

than or equal to x.

Max−Min(x,y) will return the maximum and minimum values of an array  numbers[x...y]




CODE

#include<iostream>
using namespace std;

void MinMax(int A[], int i, int j, int &max, int &min){

if(i==j){
min = A[i];
max = A[i];
return ;
}
else if(j-i == 1){

if(A[i]<=A[j]){
max = A[j];
min = A[i];
}
else
{
min = A[j];
max = A[i];
}
return;
}
else{
int mid,max1= -99999 , min1= 9999;
        mid=(i+j)/2;
        MinMax(A,i,mid,max,min);  
        MinMax(A,mid+1,j,max1,min1);

        if(max<max1)
        {
            max=max1; 
        }
        if(min>min1)
        {
             min=min1; 
        }
}
return ;

}

int main(){

int n;
cout<<"\n Enter the size of Array ";
cin>>n;
int A[n];
for(int i=0;i<n;i++){
cout<<"\nEnter ["<<i<<"] element ";
cin>>A[i];
}

int max= A[0], min = A[0];

cout<<"\nMinimum and Maximum No. in Array Using Divide and Conquer Method is :";
MinMax(A,0,n-1,max,min);
cout<<"\n\t Maximum No. in Array is "<<max;
cout<<"\n\t Minimum No. in Array is "<<min;
cout<<endl;

return 0;
}

OUTPUT



Comments

Post a Comment